package code1.dp;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 原题链接：https://leetcode.cn/problems/word-break/
 */
public class P139 {

    //完全背包问题
    //dp[i]表示从第1个字符到第i个字符的子串能否组成
    //单词之间顺序有要求，为求排列的类型
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet=new HashSet<>(wordDict);       //字典集合
        int n=s.length();                //背包容量
        boolean[] dp=new boolean[n+1];
        dp[0]=true;
        for(int i=1;i<=n;i++){          //遍历背包
            for(int j=0;j<i;j++){       //遍历物品
                if(wordSet.contains(s.substring(j,i)) && dp[j]){      //如果s从[j,i)构成的子串是字典里的单词，并且dp[j]能构成,则dp[i]能构成
                    dp[i]=true;
                }
            }
        }
        return dp[n];
    }

}
